/*
*

	*

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个
子数组

	，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。

请你返回 最小 的绝对差值。

子数组 是数组中连续的 非空 元素序列。

示例 1：

输入：nums = [1,2,4,5], k = 3

输出：0

解释：

子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。

示例 2：

输入：nums = [1,3,1,3], k = 2

输出：1

解释：

子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。

示例 3：

输入：nums = [1], k = 10

输出：9

解释：

只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 109

  - @author ala
  - @date 2024-10-09 09:26
*/
package main

import (
	"fmt"
	"math"
	"math/bits"
)

func main() {
	//nums := []int{1, 2, 4, 5}
	//k := 3

	//nums := []int{1, 3, 1, 3}
	//k := 2

	//nums := []int{1}
	//k := 10

	//nums := []int{6}
	//k := 2

	//nums := []int{20, 10, 7, 4, 65}
	//k := 14

	nums := []int{42, 70, 64, 40, 36}
	k := 88

	fmt.Println(minimumDifference(nums, k))
}

func minimumDifference(nums []int, k int) int {
	return V1(nums, k)
}

/**
 *	1）滑窗，并维护窗口内or值
 *		随着窗口增大，or值也增大。窗口减小，or值也减小
 *		维护：
 *			窗口内or值
 *			窗口内每个位置1的个数
 *	2）滑窗过程：
 *		r右移，如果or值大于k，l右移
 *		并且窗口每增大或缩小一次就记录下当前 |k - or|
 */
func V1(nums []int, k int) int {
	N, or := len(nums), 0
	bitArr := make([]int, 32)
	l, r, mn := 0, -1, math.MaxInt32
	for r < N-1 {
		r++
		or = moveRight(nums[r], or, bitArr)
		for l < r && or > k {
			mn = min(mn, abs(k-or))
			or = moveLeft(nums[l], or, bitArr)
			l++
		}
		if or == k {
			return 0
		}
		mn = min(mn, abs(k-or))
	}
	return mn
}
func abs(n int) int {
	if n < 0 {
		return -n
	} else {
		return n
	}
}
func moveRight(n, or int, bitArr []int) int {
	t := uint32(n)
	for t > 0 {
		lb := t & -t
		t -= lb
		bitArr[31-bits.LeadingZeros32(lb)]++
	}
	return or | n
}
func moveLeft(n, or int, bitArr []int) int {
	t := uint32(n)
	for t > 0 {
		lb := t & -t
		t -= lb
		i := 31 - bits.LeadingZeros32(lb)
		bitArr[i]--
		if bitArr[i] == 0 {
			or &= ^int(lb)
		}
	}
	return or
}
